package 十大算法;

/**
 * LeetCode——reorder-list（链表重排序）
 * <p>
 * <p>
 * 知识点：链表
 * 题目描述
 * <p>
 * Given a singly linked list$ L: L_0→L_1→…→L{n-1}→L_n​$, reorder it to: $L_0→L_n →L_1→L_{n-1}→L_2→L_{n-2}→…​$
 * <p>
 * You must do this in-place without altering the nodes' values.
 * <p>
 * For example, Given{1,2,3,4}, reorder it to{1,4,2,3}.
 * <p>
 * 给定一个链表$ L: L_0→L_1→…→L{n-1}→L_n$, 将其重排序为： $L_0→L_n →L_1→L_{n-1}→L_2→L_{n-2}→…​$ 你必须在不改变节点值的情况下完成。 比如： 给定{1,2,3,4},重排序为：{1,4,2,3}
 * <p>
 * 解题思路
 * <p>
 * 比如：$ L: L_0→L_1→…→L{n-1}→L_n​$，首先利用快慢指针将该链表分为两个部分：
 * <p>
 * $L_a:L_0→L_1→…L_{\frac{n}{2}}$,
 * <p>
 * $L_b:L_{\frac{n}{2}+1}→L_{\frac{n}{2}+2}→…L_{n}$
 * <p>
 * 然后将$L_b$翻转，然后合并$L_a$和$L_b$即可。
 *
 * @author tingwen
 * @date date
 */
class LinkNode {
    int value;
    LinkNode next;

    LinkNode(int x) {
        value = x;
        next = null;
    }
}

public class ReorderList {


    public void reorderList(LinkNode linkNode) {
        if (linkNode != null && linkNode.next != null) {
            LinkNode fast, slow;
            fast = slow = linkNode;

            //1、 通过快慢结点找出中间结点
            while (fast.next != null && fast.next.next != null) {
                fast = fast.next.next;
                slow = slow.next;
            }// 此时的slow 为中间结点

            //2、 将链表拆分
            LinkNode preNode = slow.next;
            slow.next = null;
            //3、将middleNode链表翻转
            LinkNode afterNode = preNode.next;
            preNode.next = null;
            while (afterNode != null) {
                LinkNode tempNode = afterNode.next;
                afterNode.next = preNode;
                preNode = afterNode;
                afterNode = tempNode;
            }// 此时的preNode 翻转后的链表

            //4、合并链表，一个一个插入
            while (preNode != null && linkNode != null) {
                LinkNode link1 = linkNode.next;
                LinkNode link2 = preNode.next;
                linkNode.next = preNode;
                preNode.next = link1;
                linkNode = link1;
                preNode = link2;
            }


        }
    }

    public static void main(String args[]) {
        LinkNode head = new LinkNode(1);
        LinkNode node2 = new LinkNode(2);
        LinkNode node3 = new LinkNode(3);
        LinkNode node4 = new LinkNode(4);
        LinkNode node5 = new LinkNode(5);

        head.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        ReorderList solution = new ReorderList();
        solution.reorderList(head);
        System.out.println("solution = " + solution);
    }

}
